﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;

/*
int n, x, ans;

int main() {
	cin >> n >> x;
	ans = 1;
	for (int i = 1; i <= x; i++) {
		ans = ans * n;
	}
	cout << ans << endl;
	return 0;
}*/

// 快速幂，前置进制转化
// 十转二 logx
/*int b[1005],j = 0; // 保存二进制,j为下标
int x;
int main() {
	cin >> x;
	if (x == 0) cout << x;
	else {
		while (x != 0) {
			j++;
			b[j] = x % 2;
			x /= 2;
		}
		for (int i = j; i >= 1; i--) {
			cout << b[i];
		}
	}	
	return 0;
}*/

// 快速幂  -- logx

// 求5的10次方，拆成5^(8+2)  因为10的二进制为1010，即1*(2^3)+0*(2^2)+1*(2^1)+0*(2^0)
// 正好与8+2对应

// 求n的x次方

/*int n, x, j;
int ans = 1;
int main() {
	cin >> n >> x;
	while (x != 0) {
		j = x % 2;  // j为x二级制某一位
		if (j == 1) {
			ans *= n;
		}
		n *= n;  // 进制越高，n*n的次数越多，二进制是两个n相乘，三进制就是3个
		x /= 2;
	}
	// 以10为例：二进制的话，为1010，是8+2，第一次是²，第二次4次方，第三次为8次方，每次乘2个
	// 三进制的话，为101，是9+1，第一次为n=n*n*n,为m³，第二次为9次方，第三次为27次方
	// 当次方高时，例如100次方，就需要使用for,那么时间复杂度就变大了，而且高位进制考虑的余数多。。。。
	cout << ans;
	return 0;
}*/


// 洛谷1226
// (a*b)%c = (a%c)*(b%c)%c
/* 模运算的运算法制
* 设	a%c=x-->a=i*c+x;
*   b%c=y-->b=j*c+y;
*	(a*b)%c = ((i*c+x)*(j*c+y))%c=0+(x*y)%c
*	(a%c)*(b%c)%c --> (x*y)%c
*/

/*
long long a, b, p, j, n, m;
long long ans = 1;
int main() {
	cin >> a >> b >> p;
	n = a, m = b;
	while (b != 0) {
		j = b % 2;  // j为b二级制某一位
		if (j == 1) {
			ans = (ans * a) % p;
		}
		a = (a * a) % p;
		b /= 2;
	}
	cout << n << "^" << m << " mod " << p << "=" << ans % p << endl;
	return 0;
}*/
